package com.copa.l107;

import java.util.*;

/**
 * @author copa
 * @createDate 2022-05-19 11:37
 * @function BFS
 */
public class Test2 {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<>();
        if (Objects.isNull(root)) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        bfs(result, queue);
        return result;
    }

    private void bfs(LinkedList<List<Integer>> result, Queue<TreeNode> queue) {
        while (queue.size() > 0) {
            List<Integer> tempList = new LinkedList<>();
            int size = queue.size();
            while (size > 0) {
                TreeNode temp = queue.poll();
                if (temp.left != null) {
                    queue.add(temp.left);
                }
                if (temp.right != null) {
                    queue.add(temp.right);
                }
                tempList.add(temp.val);
                size--;
            }
            // 因为是双向链表，所以可以插入到头结点
            result.addFirst(tempList);
        }
    }

//    public List<List<Integer>> levelOrderBottom(TreeNode root) {
//        List<List<Integer>> result = new ArrayList<>();
//        if (Objects.isNull(root)) {
//            return result;
//        }
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.add(root);
//        bfs(result, queue);
//        // 投机取巧，使用反转集合方法
//        Collections.reverse(result);
//        return result;
//    }
//
//    private void bfs(List<List<Integer>> result, Queue<TreeNode> queue) {
//        while (queue.size() > 0) {
//            List<Integer> tempList = new ArrayList<>();
//            int size = queue.size();
//            while (size > 0) {
//                TreeNode temp = queue.poll();
//                if (temp.left != null) {
//                    queue.add(temp.left);
//                }
//                if (temp.right != null) {
//                    queue.add(temp.right);
//                }
//                tempList.add(temp.val);
//                size--;
//            }
//            result.add(tempList);
//        }
//    }

    public static void main(String[] args) {
        TreeNode left = new TreeNode(9);
        TreeNode right = new TreeNode(20);
        right.left = new TreeNode(15);
        right.right = new TreeNode(7);
        TreeNode root = new TreeNode(3, left, right);
        List<List<Integer>> result = new Test2().levelOrderBottom(root);
        for (List<Integer> list : result) {
            System.out.println(Arrays.toString(list.toArray()));
        }
    }
}
